/*
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：
输入：label = 26
输出：[1,2,6,10,26]

提示：
1 <= label <= 10^6
*/


class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> res;//结果
        while(label>1)//先放入正常顺序的该节点路径
        {
            res.push_back(label);//放入当前节点
            label/=2;//父节点
        }
        res.push_back(1);//放入根节点
        reverse(res.begin(),res.end());//修改顺序为从根节点开始
        int size=res.size();//当前路径节点个数
        for(int i=size-2;i>0;i-=2)//修改其中的节点 从最后一个节点出发 隔一项才需要修正
        {
            int temp=res[i];//当前数值
            int n=0;//找2的幂
            while(pow(2,n)<res[i])
                n++;//比当前数值小的2的幂
            if(pow(2,n)>res[i])
                n--;//修正n保证2的n次幂小于等于当前数值
            int start=pow(2,n);//当前行节点的最小值
            int end=pow(2,n+1)-1;//当前行节点的最大值
            res[i]=start+end-temp;//数值反转，即升序第i个变为降序第i个
        }
        return res;
    }
};
